
 <!DOCTYPE HTML>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
  
    <title>面试精选：链表问题集锦 | Jark&#39;s Blog</title>
    <meta name="viewport" content="width=device-width, initial-scale=1,user-scalable=no">
    
    <meta name="author" content="WuChong">
    
    <meta name="description" itemprop="description" content="链表问题在面试过程中也是很重要也很基础的一部分，链表本身很灵活，很考查编程功底，所以是很值得考的地方。我将复习过程中觉得比较好的链表问题整理了下。">
    
    
    <meta name="description" content="链表问题在面试过程中也是很重要也很基础的一部分，链表本身很灵活，很考查编程功底，所以是很值得考的地方。我将复习过程中觉得比较好的链表问题整理了下。">
<meta property="og:type" content="article">
<meta property="og:title" content="面试精选：链表问题集锦">
<meta property="og:url" content="http://wuchong.me/blog/2014/03/25/interview-link-questions/">
<meta property="og:site_name" content="Jark's Blog">
<meta property="og:description" content="链表问题在面试过程中也是很重要也很基础的一部分，链表本身很灵活，很考查编程功底，所以是很值得考的地方。我将复习过程中觉得比较好的链表问题整理了下。">
<meta property="og:image" content="http://ww2.sinaimg.cn/large/81b78497tw1eesdi7bb2kj20d403qaa0.jpg">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="面试精选：链表问题集锦">
<meta name="twitter:description" content="链表问题在面试过程中也是很重要也很基础的一部分，链表本身很灵活，很考查编程功底，所以是很值得考的地方。我将复习过程中觉得比较好的链表问题整理了下。">
<meta name="twitter:creator" content="@jarkwu">
<link rel="publisher" href="111190881341800841449">

    
    <link rel="alternative" href="/atom.xml" title="Jark&#39;s Blog" type="application/atom+xml">
    
    
    <link rel="icon" href="/img/favicon.ico">
    
    
    <link rel="apple-touch-icon" href="/img/jacman.jpg">
    <link rel="apple-touch-icon-precomposed" href="/img/jacman.jpg">
    
    <link rel="stylesheet" href="/css/style.css" type="text/css">
</head>

  <body>
    <header>
      <div>
		
			<div id="imglogo">
				<a href="/"><img src="/img/logo.png" alt="Jark&#39;s Blog" title="Jark&#39;s Blog"/></a>
			</div>
			
			<div id="textlogo">
				<h1 class="site-name"><a href="/" title="Jark&#39;s Blog">Jark&#39;s Blog</a></h1>
				<h2 class="blog-motto">当你的才华还撑不起你的野心时，你就应该静下心来学习。</h2>
			</div>
			<div class="navbar"><a class="navbutton navmobile" href="#" title="菜单">
			</a></div>
			<nav class="animated">
				<ul>
					<ul>
					 
						<li><a href="/">首页</a></li>
					
						<li><a href="/archives">归档</a></li>
					
						<li><a href="/about">关于</a></li>
					
					<li>
 					
						<form class="search" action="http://zhannei.baidu.com/cse/search" target="_blank">
							<label>Search</label>
						<input name="s" type="hidden" value= 783281470518440642 ><input type="text" name="q" size="30" placeholder="搜索"><br>
						</form>
					
					</li>
				</ul>
			</nav>			
</div>
    </header>
    <div id="container">
      <div id="main" class="post" itemscope itemprop="blogPost">
  
	<article itemprop="articleBody"> 
		<header class="article-info clearfix">
  <h1 itemprop="name">
    
      <a href="/blog/2014/03/25/interview-link-questions/" title="面试精选：链表问题集锦" itemprop="url">面试精选：链表问题集锦</a>
  </h1>
  <p class="article-author">By
       
		<a href="https://plus.google.com/111190881341800841449?rel=author" title="WuChong" target="_blank" itemprop="author">WuChong</a>
		
  <p class="article-time">
    <time datetime="2014-03-25T14:58:06.000Z" itemprop="datePublished"> 发表于 2014-03-25</time>
    
  </p>
</header>
	<div class="article-content">
		
		<div id="toc" class="toc-article">
			<strong class="toc-title">文章目录</strong>
		
		<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#1-_在O(1)时间删除链表节点"><span class="toc-text">1. 在O(1)时间删除链表节点</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-_求链表倒数第k个节点"><span class="toc-text">3. 求链表倒数第k个节点</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#4-_求链表的中间节点"><span class="toc-text">4. 求链表的中间节点</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#5-_判断单链表是否存在环"><span class="toc-text">5. 判断单链表是否存在环</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#6-_找到环的入口点"><span class="toc-text">6. 找到环的入口点</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#7-_编程判断两个链表是否相交"><span class="toc-text">7. 编程判断两个链表是否相交</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#8-_扩展：链表有环，如何判断相交"><span class="toc-text">8. 扩展：链表有环，如何判断相交</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#9-_扩展：两链表相交的第一个公共节点"><span class="toc-text">9. 扩展：两链表相交的第一个公共节点</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#10-_总结"><span class="toc-text">10. 总结</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#参考文献"><span class="toc-text">参考文献</span></a></li></ol>
		
		</div>
		
		<p>链表问题在面试过程中也是很重要也很基础的一部分，链表本身很灵活，很考查编程功底，所以是很值得考的地方。我将复习过程中觉得比较好的链表问题整理了下。</p>
<p>下面是本文所要用到链表节点的定义：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
</pre></td><td class="code"><pre><span class="keyword">struct</span> Node{
    <span class="keyword">int</span> data;
    Node* next;
};
</pre></td></tr></table></figure>

<h2 id="1-_在O(1)时间删除链表节点">1. 在O(1)时间删除链表节点</h2>
<p><strong>题目描述：</strong>给定链表的头指针和一个节点指针，在O(1)时间删除该节点。[Google面试题]</p>
<p><strong>分析：</strong>本题与《编程之美》上的「从无头单链表中删除节点」类似。主要思想都是「狸猫换太子」，即用下一个节点数据覆盖要删除的节点，然后删除下一个节点。但是如果节点是尾节点时，该方法就行不通了。</p>
<p>代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
</pre></td><td class="code"><pre><span class="comment">//O(1)时间删除链表节点，从无头单链表中删除节点</span>
<span class="keyword">void</span> deleteRandomNode(Node *cur)
{
    assert(cur != NULL);
    assert(cur-&gt;next != NULL);    <span class="comment">//不能是尾节点</span>
    Node* pNext = cur-&gt;next;
    cur-&gt;data = pNext-&gt;data;
    cur-&gt;next = pNext-&gt;next;
    <span class="keyword">delete</span> pNext;
}
</pre></td></tr></table></figure><br><a id="more"></a><br>##2. 单链表的转置<br><strong>题目描述：</strong>输入一个单向链表，输出逆序反转后的链表<br><br><strong>分析：</strong>链表的转置是一个很常见、很基础的数据结构题了，非递归的算法很简单，用三个临时指针 pre、head、next 在链表上循环一遍即可。递归算法也是比较简单的，但是如果思路不清晰估计一时半会儿也写不出来吧。<br><br>下面是循环版本和递归版本的链表转置代码：<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
</pre></td><td class="code"><pre><span class="comment">//单链表的转置,循环方法</span>
Node* reverseByLoop(Node *head)
{
    <span class="keyword">if</span>(head == NULL || head-&gt;next == NULL)
        <span class="keyword">return</span> head;
    Node *pre = NULL;
    Node *next = NULL;
    <span class="keyword">while</span>(head != NULL)
    {
        next = head-&gt;next;

        head-&gt;next = pre;
        pre = head;
        head = next;
    }
    <span class="keyword">return</span> pre;
}

<span class="comment">//单链表的转置,递归方法</span>
Node* reverseByRecursion(Node *head)
{
    <span class="comment">//第一个条件是判断异常，第二个条件是结束判断</span>
    <span class="keyword">if</span>(head == NULL || head-&gt;next == NULL) 
        <span class="keyword">return</span> head;

    Node *newHead = reverseByRecursion(head-&gt;next);

    head-&gt;next-&gt;next = head;
    head-&gt;next = NULL;

    <span class="keyword">return</span> newHead;    <span class="comment">//返回新链表的头指针</span>
}
</pre></td></tr></table></figure>

<h2 id="3-_求链表倒数第k个节点">3. 求链表倒数第k个节点</h2>
<p><strong>题目描述：</strong>输入一个单向链表，输出该链表中倒数第k个节点，链表的倒数第0个节点为链表的尾指针。</p>
<p><strong>分析：</strong>设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，然后 p2 向前走 k 步，这样 p1 和 p2 之间就间隔 k 个节点，最后 p1 和 p2 同时向前移动，直至 p2 走到链表末尾。</p>
<p>代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
</pre></td><td class="code"><pre><span class="comment">//倒数第k个节点</span>
Node* theKthNode(Node *head,<span class="keyword">int</span> k)
{
    <span class="keyword">if</span>(k &lt; <span class="number">0</span>) <span class="keyword">return</span> NULL;    <span class="comment">//异常判断</span>

    Node *slow,*fast;
    slow = fast = head;
    <span class="keyword">int</span> i = k;
    <span class="keyword">for</span>(;i&gt;<span class="number">0</span> && fast!=NULL;i--)
    {
        fast = fast-&gt;next;
    }

    <span class="keyword">if</span>(i &gt; <span class="number">0</span>)    <span class="keyword">return</span> NULL;    <span class="comment">//考虑k大于链表长度的case</span>

    <span class="keyword">while</span>(fast != NULL)
    {
        slow = slow-&gt;next;
        fast = fast-&gt;next;
    }

    <span class="keyword">return</span> slow;
}
</pre></td></tr></table></figure>

<h2 id="4-_求链表的中间节点">4. 求链表的中间节点</h2>
<p><strong>题目描述：</strong>求链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。</p>
<p><strong>分析：</strong>此题的解决思路和第3题「求链表的倒数第 k 个节点」很相似。可以先求链表的长度，然后计算出中间节点所在链表顺序的位置。但是如果要求只能扫描一遍链表，如何解决呢？最高效的解法和第3题一样，通过两个指针来完成。用两个指针从链表头节点开始，一个指针每次向后移动两步，一个每次移动一步，直到快指针移到到尾节点，那么慢指针即是所求。</p>
<p>代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
</pre></td><td class="code"><pre><span class="comment">//求链表的中间节点</span>
Node* theMiddleNode(Node *head)
{
    <span class="keyword">if</span>(head == NULL)
        <span class="keyword">return</span> NULL;
    Node *slow,*fast;
    slow = fast = head;
    <span class="comment">//如果要求在链表长度为偶数的情况下，返回中间两个节点的第一个，可以用下面的循环条件</span>
    <span class="comment">//while(fast && fast-&gt;next != NULL && fast-&gt;next-&gt;next != NULL)  </span>
    <span class="keyword">while</span>(fast != NULL && fast-&gt;next != NULL)
    {
        fast = fast-&gt;next-&gt;next;
        slow = slow-&gt;next;
    }
    <span class="keyword">return</span> slow;
}
</pre></td></tr></table></figure>

<h2 id="5-_判断单链表是否存在环">5. 判断单链表是否存在环</h2>
<p><strong>题目描述：</strong>输入一个单向链表，判断链表是否有环？</p>
<p><strong>分析：</strong>通过两个指针，分别从链表的头节点出发，一个每次向后移动一步，另一个移动两步，两个指针移动速度不一样，如果存在环，那么两个指针一定会在环里相遇。</p>
<p>代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
</pre></td><td class="code"><pre><span class="comment">//判断单链表是否存在环,参数circleNode是环内节点，后面的题目会用到</span>
<span class="keyword">bool</span> hasCircle(Node *head,Node *&circleNode)
{
    Node *slow,*fast;
    slow = fast = head;
    <span class="keyword">while</span>(fast != NULL && fast-&gt;next != NULL)
    {
        fast = fast-&gt;next-&gt;next;
        slow = slow-&gt;next;
        <span class="keyword">if</span>(fast == slow)
        {
            circleNode = fast;
            <span class="keyword">return</span> <span class="keyword">true</span>;
        }
    }

    <span class="keyword">return</span> <span class="keyword">false</span>;
}
</pre></td></tr></table></figure>

<h2 id="6-_找到环的入口点">6. 找到环的入口点</h2>
<p><strong>题目描述：</strong>输入一个单向链表，判断链表是否有环。如果链表存在环，如何找到环的入口点？</p>
<p><strong>解题思路：</strong> 由上题可知，按照 p2 每次两步，p1 每次一步的方式走，发现 p2 和 p1 重合，确定了单向链表有环路了。接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当 p1 和 p2 再次相遇的时候，就是环路的入口了。</p>
<p><strong>为什么？：</strong>假定起点到环入口点的距离为 a，p1 和 p2 的相交点M与环入口点的距离为b，环路的周长为L，当 p1 和 p2 第一次相遇的时候，假定 p1 走了 n 步。那么有：</p>
<p>p1走的路径： <code>a+b ＝ n</code>；<br>p2走的路径： <code>a+b+k*L = 2*n</code>；         p2 比 p1 多走了k圈环路，总路程是p1的2倍</p>
<p>根据上述公式可以得到 <code>k*L=a+b=n</code>显然，如果从相遇点M开始，p1 再走 n 步的话，还可以再回到相遇点，同时p2从头开始走的话，经过n步，也会达到相遇点M。</p>
<p>显然在这个步骤当中 p1 和 p2 只有前 a 步走的路径不同，所以当 p1 和 p2 再次重合的时候，必然是在链表的环路入口点上。</p>
<p>代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
</pre></td><td class="code"><pre><span class="comment">//找到环的入口点</span>
Node* findLoopPort(Node *head)
{
    Node *slow,*fast;
    slow = fast = head;

    <span class="comment">//先判断是否存在环</span>
    <span class="keyword">while</span>(fast != NULL && fast-&gt;next != NULL)
    {
        fast = fast-&gt;next-&gt;next;
        slow = slow-&gt;next;
        <span class="keyword">if</span>(fast == slow)
            <span class="keyword">break</span>;
    }

    <span class="keyword">if</span>(fast != slow) <span class="keyword">return</span> NULL;    <span class="comment">//不存在环</span>

    fast = head;                <span class="comment">//快指针从头开始走，步长变为1</span>
    <span class="keyword">while</span>(fast != slow)            <span class="comment">//两者相遇即为入口点</span>
    {
        fast = fast-&gt;next;
        slow = slow-&gt;next;
    }

    <span class="keyword">return</span> fast;
}
</pre></td></tr></table></figure>

<h2 id="7-_编程判断两个链表是否相交">7. 编程判断两个链表是否相交</h2>
<p><strong>题目描述：</strong>给出两个单向链表的头指针（如下图所示），</p>
<p><img src="http://ww2.sinaimg.cn/large/81b78497tw1eesdi7bb2kj20d403qaa0.jpg" alt=""></p>
<p>比如h1、h2，判断这两个链表是否相交。这里为了简化问题，我们假设两个链表均不带环。</p>
<p><strong>解题思路：</strong></p>
<ol>
<li><p>直接循环判断第一个链表的每个节点是否在第二个链表中。但，这种方法的时间复杂度为O(Length(h1) * Length(h2))。显然，我们得找到一种更为有效的方法，至少不能是O（N^2）的复杂度。</p>
</li>
<li><p>针对第一个链表直接构造hash表，然后查询hash表，判断第二个链表的每个节点是否在hash表出现，如果所有的第二个链表的节点都能在hash表中找到，即说明第二个链表与第一个链表有相同的节点。时间复杂度为为线性：O(Length(h1) + Length(h2))，同时为了存储第一个链表的所有节点，空间复杂度为O(Length(h1))。是否还有更好的方法呢，既能够以线性时间复杂度解决问题，又能减少存储空间？</p>
</li>
<li><p>转换为环的问题。把第二个链表接在第一个链表后面，如果得到的链表有环，则说明两个链表相交。如何判断有环的问题上面已经讨论过了，但这里有更简单的方法。因为如果有环，则第二个链表的表头一定也在环上，即第二个链表会构成一个循环链表，我们只需要遍历第二个链表，看是否会回到起始点就可以判断出来。这个方法的时间复杂度是线性的，空间是常熟。</p>
</li>
<li><p>进一步考虑“如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的”这个特点，我们可以知道，如果它们相交，则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点，所以这成了我们简化解法的一个主要突破口。那么，我们只要判断两个链表的尾指针是否相等。相等，则链表相交；否则，链表不相交。<br>所以，先遍历第一个链表，记住最后一个节点。然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则，不相交。这样我们就得到了一个时间复杂度，它为O((Length(h1) + Length(h2))，而且只用了一个额外的指针来存储最后一个节点。这个方法时间复杂度为线性O(N)，空间复杂度为O(1)，显然比解法三更胜一筹。</p>
</li>
</ol>
<p>解法四的代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
</pre></td><td class="code"><pre><span class="comment">//判断两个链表是否相交</span>
<span class="keyword">bool</span> isIntersect(Node *h1,Node *h2)
{
    <span class="keyword">if</span>(h1 == NULL || h2 == NULL) <span class="keyword">return</span> <span class="keyword">false</span>;    <span class="comment">//异常判断</span>
    <span class="keyword">while</span>(h1-&gt;next != NULL)
    {
        h1 = h1-&gt;next;
    }

    <span class="keyword">while</span>(h2-&gt;next != NULL)
    {
        h2 = h2-&gt;next;
    }

    <span class="keyword">if</span>(h1 == h2) <span class="keyword">return</span> <span class="keyword">true</span>;        <span class="comment">//尾节点是否相同</span>
    <span class="keyword">else</span> <span class="keyword">return</span> <span class="keyword">false</span>;
}
</pre></td></tr></table></figure>

<h2 id="8-_扩展：链表有环，如何判断相交">8. 扩展：链表有环，如何判断相交</h2>
<p><strong>题目描述：</strong>上面的问题都是针对链表无环的，那么如果现在，链表是有环的呢?上面的方法还同样有效么?</p>
<p><strong>分析：</strong>如果有环且两个链表相交，则两个链表都有共同一个环，即环上的任意一个节点都存在于两个链表上。因此，就可以判断一链表上俩指针相遇的那个节点，在不在另一条链表上。</p>
<p>代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
</pre></td><td class="code"><pre><span class="comment">//判断两个带环链表是否相交</span>
<span class="keyword">bool</span> isIntersectWithLoop(Node *h1,Node *h2)
{
    Node *circleNode1,*circleNode2;
    <span class="keyword">if</span>(!hasCircle(h1,circleNode1))    <span class="comment">//判断链表带不带环，并保存环内节点</span>
        <span class="keyword">return</span> <span class="keyword">false</span>;                <span class="comment">//不带环，异常退出</span>
    <span class="keyword">if</span>(!hasCircle(h2,circleNode2))
        <span class="keyword">return</span> <span class="keyword">false</span>;

    Node *temp = circleNode2-&gt;next;
    <span class="keyword">while</span>(temp != circleNode2)
    {
        <span class="keyword">if</span>(temp == circleNode1)
            <span class="keyword">return</span> <span class="keyword">true</span>;
        temp = temp-&gt;next;
    }
    <span class="keyword">return</span> <span class="keyword">false</span>;
}
</pre></td></tr></table></figure>

<h2 id="9-_扩展：两链表相交的第一个公共节点">9. 扩展：两链表相交的第一个公共节点</h2>
<p><strong>题目描述：</strong>如果两个无环单链表相交，怎么求出他们相交的第一个节点呢？</p>
<p><strong>分析：</strong>采用对齐的思想。计算两个链表的长度 L1 , L2，分别用两个指针 p1 , p2 指向两个链表的头，然后将较长链表的 p1（假设为 p1）向后移动<code>L2 - L1</code>个节点，然后再同时向后移动p1 , p2，直到 <code>p1 = p2</code>。相遇的点就是相交的第一个节点。</p>
<p>代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
</pre></td><td class="code"><pre><span class="comment">//求两链表相交的第一个公共节点</span>
Node* findIntersectNode(Node *h1,Node *h2)
{
    <span class="keyword">int</span> len1 = listLength(h1);          <span class="comment">//求链表长度</span>
    <span class="keyword">int</span> len2 = listLength(h2);
    <span class="comment">//对齐两个链表</span>
    <span class="keyword">if</span>(len1 &gt; len2)
    {
        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;len1-len2;i++)
            h1=h1-&gt;next;
    }
    <span class="keyword">else</span> 
    {
        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;len2-len1;i++)
            h2=h2-&gt;next;
    }

    <span class="keyword">while</span>(h1 != NULL)
    {
        <span class="keyword">if</span>(h1 == h2)
            <span class="keyword">return</span> h1;
        h1 = h1-&gt;next;
        h2 = h2-&gt;next;    
    }
    <span class="keyword">return</span> NULL;
}
</pre></td></tr></table></figure>

<h2 id="10-_总结">10. 总结</h2>
<p>可以发现，在链表的问题中，通过两个的指针来提高效率是很值得考虑的一个解决方案，所以一定要记住这种解题思路。记住几种典型的链表问题解决方案，很多类似的题目都可以转换到熟悉的问题再解决。</p>
<h2 id="参考文献">参考文献</h2>
<ul>
<li><a href="http://blog.csdn.net/v_JULY_v/article/details/6447013" target="_blank" rel="external">程序员编程艺术：第九章、闲话链表追赶问题</a></li>
<li><a href="http://www.cppblog.com/humanchao/archive/2008/04/17/47357.html" target="_blank" rel="external">判断单链表是否存在环，判断两个链表是否相交问题详解</a></li>
<li><a href="http://blog.csdn.net/anonymalias/article/details/11020477" target="_blank" rel="external">面试算法之链表操作集锦</a></li>
</ul>
  
	</div>
		<footer class="article-footer clearfix">
<div class="article-catetags">

<div class="article-categories">
  <span></span>
  <a class="article-category-link" href="/categories/程序设计/">程序设计</a>
</div>


  <div class="article-tags">
  
  <span></span> <a href="/tags/面试/">面试</a><a href="/tags/算法/">算法</a>
  </div>

</div>



	<div class="article-share" id="share">
	
	  <div data-url="http://wuchong.me/blog/2014/03/25/interview-link-questions/" data-title="面试精选：链表问题集锦 | Jark&#39;s Blog" data-tsina="2176287895" class="share clearfix">
	  </div>
	
	</div>


</footer>

   	       
	</article>
	
<nav class="article-nav clearfix">
 
 <div class="prev" >
 <a href="/blog/2014/04/19/recsys-cf-study/" title="推荐系统学习：协同过滤实现">
  <strong>上一篇：</strong><br/>
  <span>
  推荐系统学习：协同过滤实现</span>
</a>
</div>


<div class="next">
<a href="/blog/2014/03/17/string-to-int/"  title="字符串转换成整数——从源码学习">
 <strong>下一篇：</strong><br/> 
 <span>字符串转换成整数——从源码学习
</span>
</a>
</div>

</nav>

	
<section id="comments" class="comment">
	<div class="ds-thread" data-thread-key="blog/2014/03/25/interview-link-questions/" data-title="面试精选：链表问题集锦" data-url="http://wuchong.me/blog/2014/03/25/interview-link-questions/"></div>
</section>


</div>  
      <div class="openaside"><a class="navbutton" href="#" title="显示侧边栏"></a></div>

<div id="asidepart">
<div class="closeaside"><a class="closebutton" href="#" title="隐藏侧边栏"></a></div>
<aside class="clearfix">

  
<div class="categorieslist">
	<p class="asidetitle">分类</p>
		<ul>
		
			<li><a href="/categories/Hexo/" title="Hexo">Hexo<sup>7</sup></a></li>
		
			<li><a href="/categories/LinuxUnix/" title="Linux/Unix">Linux/Unix<sup>6</sup></a></li>
		
			<li><a href="/categories/Python/" title="Python">Python<sup>3</sup></a></li>
		
			<li><a href="/categories/推荐系统/" title="推荐系统">推荐系统<sup>3</sup></a></li>
		
			<li><a href="/categories/杂项资源/" title="杂项资源">杂项资源<sup>2</sup></a></li>
		
			<li><a href="/categories/程序设计/" title="程序设计">程序设计<sup>5</sup></a></li>
		
			<li><a href="/categories/系统架构/" title="系统架构">系统架构<sup>1</sup></a></li>
		
			<li><a href="/categories/编程语言/" title="编程语言">编程语言<sup>2</sup></a></li>
		
			<li><a href="/categories/职场生涯/" title="职场生涯">职场生涯<sup>2</sup></a></li>
		
			<li><a href="/categories/随笔生活/" title="随笔生活">随笔生活<sup>5</sup></a></li>
		
		</ul>
</div>


  
<div class="tagslist">
	<p class="asidetitle">标签</p>
		<ul class="clearfix">
		
			<li><a href="/tags/Hexo/" title="Hexo">Hexo<sup>8</sup></a></li>
		
			<li><a href="/tags/面试/" title="面试">面试<sup>5</sup></a></li>
		
			<li><a href="/tags/Linux基础/" title="Linux基础">Linux基础<sup>5</sup></a></li>
		
			<li><a href="/tags/生活/" title="生活">生活<sup>4</sup></a></li>
		
			<li><a href="/tags/博客/" title="博客">博客<sup>4</sup></a></li>
		
			<li><a href="/tags/Python/" title="Python">Python<sup>4</sup></a></li>
		
			<li><a href="/tags/阿里推荐大赛/" title="阿里推荐大赛">阿里推荐大赛<sup>4</sup></a></li>
		
			<li><a href="/tags/算法/" title="算法">算法<sup>2</sup></a></li>
		
			<li><a href="/tags/爬虫/" title="爬虫">爬虫<sup>2</sup></a></li>
		
			<li><a href="/tags/ODPS/" title="ODPS">ODPS<sup>2</sup></a></li>
		
			<li><a href="/tags/教程/" title="教程">教程<sup>2</sup></a></li>
		
			<li><a href="/tags/Jacman/" title="Jacman">Jacman<sup>2</sup></a></li>
		
			<li><a href="/tags/Java/" title="Java">Java<sup>2</sup></a></li>
		
			<li><a href="/tags/文件系统/" title="文件系统">文件系统<sup>2</sup></a></li>
		
			<li><a href="/tags/启动流程/" title="启动流程">启动流程<sup>1</sup></a></li>
		
			<li><a href="/tags/权限/" title="权限">权限<sup>1</sup></a></li>
		
			<li><a href="/tags/正则表达式/" title="正则表达式">正则表达式<sup>1</sup></a></li>
		
			<li><a href="/tags/jQuery/" title="jQuery">jQuery<sup>1</sup></a></li>
		
			<li><a href="/tags/双检锁/" title="双检锁">双检锁<sup>1</sup></a></li>
		
			<li><a href="/tags/设计模式/" title="设计模式">设计模式<sup>1</sup></a></li>
		
		</ul>
</div>


  <div class="linkslist">
  <p class="asidetitle">友情链接</p>
    <ul>
        
          <li>
            <a href="https://coderq.com" target="_blank" title="码农圈">码农圈</a>
          </li>
        
          <li>
            <a href="http://zipperary.com/" target="_blank" title="Zippera&#39;s Blog">Zippera&#39;s Blog</a>
          </li>
        
          <li>
            <a href="http://hijiangtao.github.io/" target="_blank" title="Data.Blog">Data.Blog</a>
          </li>
        
    </ul>
</div>

  <div class="weiboshow">
  <p class="asidetitle">新浪微博</p>
    <iframe width="100%" height="119" class="share_self"  frameborder="0" scrolling="no" src="http://widget.weibo.com/weiboshow/index.php?language=&width=0&height=119&fansRow=2&ptype=1&speed=0&skin=9&isTitle=1&noborder=1&isWeibo=0&isFans=0&uid=2176287895&verifier=b3593ceb&dpc=1"></iframe>
</div>


  <div class="rsspart">
	<a href="/atom.xml" target="_blank" title="rss">RSS 订阅</a>
</div>

</aside>
</div>
    </div>
    <footer><div id="footer" >
	
	<div class="line">
		<span></span>
		<div class="author"></div>
	</div>
	
	
	<section class="info">
		<p> Hello,I&#39;m WuChong. For now I&#39;m a graduate student in Beijing. <br/>
			I&#39;ll share my learning experience with you at this blog.</p>
	</section>
	 
	<div class="social-font" class="clearfix">
		
		<a href="http://weibo.com/wuchong1014" target="_blank" class="icon-weibo" title="微博"></a>
		
		
		<a href="https://github.com/wuchong" target="_blank" class="icon-github" title="github"></a>
		
		
		
		<a href="https://twitter.com/jarkwu" target="_blank" class="icon-twitter" title="twitter"></a>
		
		
		
		
		
		
		<a href="https://plus.google.com/111190881341800841449?rel=author" target="_blank" class="icon-google_plus" title="Google+"></a>
		
		
	</div>
		<p class="copyright">Powered by <a href="http://zespia.tw/hexo/" target="_blank" title="hexo">hexo</a> and Theme by <a href="https://github.com/wuchong/jacman" target="_blank" title="Pacman">Jacman</a> © 2014 
		
		<a href="http://wuchong.me/about" target="_blank" title="WuChong">WuChong</a>
		
		</p>
</div>
</footer>
    <script src="/js/jquery-2.0.3.min.js"></script>
<script src="/js/jquery.imagesloaded.min.js"></script>
<script src="/js/gallery.js"></script>

<script type="text/javascript">
$(document).ready(function(){ 
  $('.navbar').click(function(){
    $('header nav').toggleClass('shownav');
  });
  var myWidth = 0;
  function getSize(){
    if( typeof( window.innerWidth ) == 'number' ) {
      myWidth = window.innerWidth;
    } else if( document.documentElement && document.documentElement.clientWidth) {
      myWidth = document.documentElement.clientWidth;
    };
  };
  var m = $('#main'),
      a = $('#asidepart'),
      c = $('.closeaside'),
      o = $('.openaside');
  $(window).resize(function(){
    getSize(); 
    if (myWidth >= 1024) {
      $('header nav').removeClass('shownav');
    }else
    {
      m.removeClass('moveMain');
      a.css('display', 'block').removeClass('fadeOut');
      o.css('display', 'none');
        
    }
  });
  c.click(function(){
    a.addClass('fadeOut').css('display', 'none');
    o.css('display', 'block').addClass('fadeIn');
    m.addClass('moveMain');
  });
  o.click(function(){
    o.css('display', 'none').removeClass('beforeFadeIn');
    a.css('display', 'block').removeClass('fadeOut').addClass('fadeIn');      
    m.removeClass('moveMain');
  });
  $(window).scroll(function(){
    o.css("top",Math.max(80,260-$(this).scrollTop()));
  });
});
</script>

<script type="text/javascript">
$(document).ready(function(){ 
  var ai = $('.article-content>iframe'),
      ae = $('.article-content>embed'),
      t  = $('#toc'),
      h  = $('article h2')
      ah = $('article h2'),
      ta = $('#toc.toc-aside'),
      o  = $('.openaside'),
      c  = $('.closeaside');
  if(ai.length>0){
    ai.wrap('<div class="video-container" />');
  };
  if(ae.length>0){
   ae.wrap('<div class="video-container" />');
  };
  if(ah.length==0){
    t.css('display','none');
  }else{
    c.click(function(){
      ta.css('display', 'block').addClass('fadeIn');
    });
    o.click(function(){
      ta.css('display', 'none');
    });
    $(window).scroll(function(){
      ta.css("top",Math.max(140,320-$(this).scrollTop()));
    });
  };
});
</script>


<script type="text/javascript">
$(document).ready(function(){ 
  var $this = $('.share'),
      url = $this.attr('data-url'),
      encodedUrl = encodeURIComponent(url),
      title = $this.attr('data-title'),
      tsina = $this.attr('data-tsina'),
      description = $this.attr('description');
  var html = [
  '<a href="#" class="overlay" id="qrcode"></a>',
  '<div class="qrcode clearfix"><span>扫描二维码分享到微信朋友圈</span><a class="qrclose" href="#nothing"></a><strong>Loading...Please wait</strong><img id="qrcode-pic" data-src="http://s.jiathis.com/qrcode.php?url=' + encodedUrl + '"/></div>',
  '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="article-share-facebook" target="_blank" title="Facebook"></a>',
  '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="article-share-twitter" target="_blank" title="Twitter"></a>',
  '<a href="#qrcode" class="article-share-qrcode" title="微信"></a>',
  '<a href="http://widget.renren.com/dialog/share?resourceUrl=' + encodedUrl + '&srcUrl=' + encodedUrl + '&title=' + title +'" class="article-share-renren" target="_blank" title="人人"></a>',
  '<a href="http://service.weibo.com/share/share.php?title='+title+'&url='+encodedUrl +'&ralateUid='+ tsina +'&searchPic=true&style=number' +'" class="article-share-weibo" target="_blank" title="微博"></a>',
  '<span title="Share to"></span>'
  ].join('');
  $this.append(html);
  $('.article-share-qrcode').click(function(){
    var imgSrc = $('#qrcode-pic').attr('data-src');
    $('#qrcode-pic').attr('src', imgSrc);
    $('#qrcode-pic').load(function(){
        $('.qrcode strong').text(' ');
    });
  });
});     
</script>



<script type="text/javascript">
  var duoshuoQuery = {short_name:"wuchong"};
  (function() {
    var ds = document.createElement('script');
    ds.type = 'text/javascript';ds.async = true;
    ds.src = '//static.duoshuo.com/embed.js';
    ds.charset = 'UTF-8';
    (document.getElementsByTagName('head')[0] 
    || document.getElementsByTagName('body')[0]).appendChild(ds);
  })();
</script> 







<link rel="stylesheet" href="/fancybox/jquery.fancybox.css" media="screen" type="text/css">
<script src="/fancybox/jquery.fancybox.pack.js"></script>
<script type="text/javascript">
$(document).ready(function(){ 
  $('.article-content').each(function(i){
    $(this).find('img').each(function(){
      if ($(this).parent().hasClass('fancybox')) return;
      var alt = this.alt;
      if (alt) $(this).after('<span class="caption">' + alt + '</span>');
      $(this).wrap('<a href="' + this.src + '" title="' + alt + '" class="fancybox"></a>');
    });
    $(this).find('.fancybox').each(function(){
      $(this).attr('rel', 'article' + i);
    });
  });
  if($.fancybox){
    $('.fancybox').fancybox();
  }
}); 
</script>



<!-- Analytics Begin -->

<script type="text/javascript">
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-46321946-2', 'wuchong.me');  
ga('send', 'pageview');
</script>





<!-- Analytics End -->

<!-- Totop Begin -->

	<div id="totop">
	<a title="返回顶部"><img src="/img/scrollup.png"/></a>
	</div>
	<script src="/js/totop.js"></script>

<!-- Totop End -->

<!-- MathJax Begin -->
<!-- mathjax config similar to math.stackexchange -->


<!-- MathJax End -->

  </body>
</html>
